Con người đã có mặt trên các đảo của huyện Vân Đồn từ rất sớm. Di chỉ khảo cổ ở đây có mật độ đậm đặc. Hang Soi Nhụ là một di chỉ thuộc trung kỳ đồ đá mới, trước cả văn hóa Hạ Long. Tại thôn Ðá Bạc xã Minh Châu có di chỉ mộ cổ thời Hán.

Tên Vân Ðồn có nguồn gốc từ tên núi Vân (núi có mây phủ) ở làng Vân (nay thuộc xã Quan Lạn) nằm trong tuyến đảo ngoài Vân Hải. Do ở cửa ngõ của vùng quần đảo hiểm yếu nên, theo sử sách, năm 980 ở đây đã có đồn Vân, trấn giữ vùng biển Đông Bắc, của quân đội nhà Tiền Lê. Sang triều Lý năm 1149 vua Lý Anh Tông chính thức lập trang Vân Ðồn, đồng thời Vân Đồn biến thành thương cảng đầu tiên của Đại Việt, trong giao thương với các nước trong khu vực Đông Á và Thế giới như: Nhật Bản, Trung Quốc, Ấn Độ, Thái Lan, Indonesia... Thương cảng Vân Đồn thịnh vượng suốt 3 triều đại là: Lý - Trần - Hậu Lê (Lê sơ) rồi suy thái và bị lãng quên vào thời nhà Mạc.[4]

Di tích Thương cảng Vân Đồn còn lại vừa chứa đựng dấu ấn của nhà Trần về chiến công chống nhà Nguyên lại vừa có dấu ấn về giao thương, buôn bán. Trận Vân Đồn năm 1288 trên dòng sông Mang (Quan Lạn) gắn liền với tên tuổi của danh tướng Trần Khánh Dư. Dưới sự chỉ huy của ông, quân dân nhà Trần đã đánh tan đoàn thuyền lương của Trương Văn Hổ, góp phần quan trọng vào chiến thắng chung của trận Bạch Đằng năm 1288.

Sau khi Thương cảng Vân Đồn được hình thành từ thời Lý (1149), đến thời Trần đã phát triển tới hưng thịnh. Các bến thuyền cổ trung chuyển hàng hoá gồm hương liệu, gốm sứ, lâm thổ sản hình thành dọc ven sông Bạch Đằng, Cửa Lục cho tới các đảo Cống Đông, Quan Lạn. Tại đảo Cống Đông (nay là xã Thắng Lợi), các nhà khảo cổ đã tìm thấy dấu tích của nhiều công trình kiến trúc Phật giáo quy mô thời Trần như chùa, tháp, nhiều di vật bia đá, lan can, chân kê cột... Đây là những minh chứng rõ nhất cho sự phát triển phồn thịnh về thương mại dưới triều nhà Trần.

Trong quá trình lịch sử thì Vân Đồn đã nhiều lần thay tên và có lúc là huyện, lúc là châu. Đến tháng 12 năm 1948 thì Chính phủ nước Việt Nam Dân chủ Cộng hòa quyết định thành lập huyện Cẩm Phả (được tách ra khỏi thị xã Cẩm Phả).

Huyện Cẩm Phả khi đó gồm 16 xã: Bản Sen, Bình Dân, Cô Tô, Cộng Hòa, Đài Xuyên, Ðoàn Kết, Ðông Xá, Hạ Long, Minh Châu, Ngọc Vừng, Quan Lạn, Thạch Hà, Thanh Lân, Văn Châu, Vạn Hoa, Vạn Yên.

Ngày 26 tháng 9 năm 1966, sáp nhập xã Tân Hải thuộc thị xã Hồng Gai và xã Thắng Lợi thuộc thị xã Cẩm Phả vào huyện Cẩm Phả.[5]

Ngày 16 tháng 1 năm 1979, sáp nhập xã Văn Châu vào xã Cộng Hòa và chuyển xã này về thị xã Cẩm Phả quản lý.

Ngày 10 tháng 9 năm 1981, thành lập thị trấn Cái Rồng, sáp nhập xã Tân Hải vào xã Ngọc Vừng và sáp nhập xã Thạch Hà vào các xã Đông Xá, Hạ Long và thị trấn Cái Rồng.[6]

Ngày 16 tháng 4 năm 1988, sáp nhập xã Vạn Hoa vào xã Vạn Yên.

Đến ngày 23 tháng 3 năm 1994, huyện Cẩm Phả được đổi tên thành huyện Vân Đồn như hiện nay. Đồng thời, tách 2 xã Cô Tô, Thanh Lân để thành lập huyện đảo Cô Tô.

Ngày 21 tháng 8 năm 2015, thị trấn Cái Rồng được công nhận là đô thị loại IV.

Huyện Vân Đồn có 1 thị trấn và 11 xã như hiện nay.